#include<bits/stdc++.h>
#include"BinarySearchTree.h"
using namespace std;
int n;
vector<int> data,temp;
int main(){
    cin >> n;
    data.resize(n);
    for(int i=0;i<n;i++) cin >>data[i];
     
    temp = data;
    BST_sort(temp);
    for(int i=0;i<n;i++) cout << temp[i]<<" ";
    cout << endl;

    temp = data;
    Randomized_BST_sort(temp);
    for(int i=0;i<n;i++) cout << temp[i]<<" ";
    cout << endl;
}
